/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package commonlib.domain;

import java.util.*;

/**
 * Aquesta classe implementa un generador de regles.
 * @author genis.sole
 */
public class RuleGenerator {

    public RuleGenerator() {}

    /**
     * Calcula em minim entre tres nombres enters
     */
    private int min3(int x, int y, int z) {
        if (x > y) x = y;
        if (x > z) x = z;
        return x;
    }

    /**
     *  Comprova que i sigui mes gran que 0 si es aixi retorna i altrament 0
     */
    private int lowerLim(int i) {
        return ((i < 0) ? 0 : i);
    }
    
    /**
     * Afegeix la norma alpha -> beta a rules si aquesta és una regla acceptada.
     * Una regla acceptada es aquella en la que alpha es diferent de beta i ni
     * alpha ni beta son strings buids.
     * @param alpha es l'string que representa el camp alpha de la regla
     * @param beta es l'estring que representa el camp beta de la regla
     * @param rules es el contenidor on guardem la regla
     */
    private void addAB(StringBuilder alpha, StringBuilder beta,
                       ArrayList<ABPair> rules) {
        String a = new String(alpha);
        String b = new String(beta);
        
        if (!(a.equals(b)) && a.length() != 0 && b.length() != 0) {
                ABPair pair = new ABPair(a, b);
                rules.add(pair);
        }
    }
    
    /**
     * Aplica l'algorisme de leveinshtein per trobar la distancia d'edicio
     * minima entre dos strings i en retorna la matriu generada.
     * 
     * @param s1 es l'string al qual volem calcular la distancia
     * @param s2 es l'string respecte el que calculem la distancia
     * @return la matriu generada per l'algorisme de leveinshtein.
     */
    private int [][] levMatrix(char [] s1, char [] s2) {
        int m = s1.length;
        int n = s2.length;
        int [][] M = new int[n+1][m+1];

        for (int i = 0; i <= n; ++i) {
            M[i][0] = i;
        }
        for (int j = 0; j <= m; ++j) {
            M[0][j] = j;
        }

        for (int j = 1; j <= m; ++j) {
            for (int i = 1; i <= n; ++i) {
                if (s1[j-1] == s2[i-1]) {
                    M[i][j] = M[i-1][j-1];
                } else {
                    M[i][j] = min3(M[i-1][j-1] + 1, M[i-1][j] + 1,
                                   M[i][j-1] + 1);
                }
            }
        }
        
        return M;
    }

    /**
     * Recorre tots els possibles camins minims de la matriu des de M[i][j] fins
     * a M[ei-1][ej-1] i genera i guarda a rules les regles que es dedueixen del
     * recorregut.
     * 
     * @param M matriu generada per l'algorisme de levenshtein
     * @param s1 string *correcte* a partir del que es genera la part alpha de
     * les regles
     * @param s2 string *incorrecte* a partir del que es genera la part beta de
     * les regles
     * @param n mida maxima de les regles generades
     * @param i component i de la posicio que estem tractant
     * @param j component j de la posicio que estem tractant
     * @param ei component i del limit superior que marca la posicio de la
     * matriu on aconseguirem regles de com a molt mida n
     * @param ej component j del limit superior que marca la posicio de la
     * matriu on aconseguirem regles de coma molt mida n
     * @param marks marks matriu de marcatge per evitar solucions repetides.
     * @param rules conjunt de regles on afegirem les noves que es generin
     * @param str1 part de la regla alpha que s'ha generat fins el moment
     * @param str2 part de la regla beta que s'ha generat fins el moment
     */
    private void auxLevSubNAssociation(int [][] M, char [] s1, char [] s2,
            int n, int i, int j, int ei, int ej, boolean [][] marks,
            ArrayList<ABPair> rules, StringBuilder str1, StringBuilder str2) {
        if (i > ei && j > ej) {
            int minPath = min3(M[i-1][j-1], M[i-1][j], M[i][j-1]);
            if (minPath == M[i-1][j-1] && !marks[i-1][j-1]) {
                str1.append(s1[j-1]);
                str2.append(s2[i-1]);
                addAB (str1, str2, rules);
                marks[i-1][j-1] = true;
                auxLevSubNAssociation(M, s1, s2, n, i-1, j-1, ei, ej, marks,
                                      rules, str1, str2);
                str1.deleteCharAt(str1.length() - 1);
                str2.deleteCharAt(str2.length() - 1);
            }
            if (minPath == M[i-1][j] && !marks[i-1][j]) {
                str2.append(s2[i-1]);
                addAB (str1, str2, rules);
                marks[i-1][j] = true;
                /*
                 * Amb aquesta crida nomes generem regles on beta ńo pot superar
                 * la longitud de n.
                 * Si volem betes generals llabors la crida seria la seguent:
                 * auxLevSubNAssociation(M, s1, s2, n, i-1, j, lowerLim(ei-1),
                 *                       ej, marks, rules, str1, str2);
                 * On em canviat ei per lowerLim(ei-1).
                 */
                auxLevSubNAssociation(M, s1, s2, n, i-1, j, ei, ej, marks,
                                      rules, str1, str2);
                str2.deleteCharAt(str2.length() - 1);
            }
            if (minPath == M[i][j-1] && !marks[i][j-1]) {
                str1.append(s1[j-1]);
                addAB (str1, str2, rules);
                marks[i][j-1] = true;
                /*
                 * Amb aquesta crida nomes generem regles on alpha ńo pot
                 * superar la longitud de n.
                 * Si volem alphes generals llabors la crida seria la seguent:
                 * auxLevSubNAssociation(M, s1, s2, n, i, j-1, ei,
                 *         lowerLim(ej-1), marks, rules, str1, str2);
                 * On em canviat ej per lowerLim(ej-1).
                 */
                auxLevSubNAssociation(M, s1, s2, n, i, j-1, ei, ej, marks,
                                      rules, str1, str2);
                str1.deleteCharAt(str1.length() - 1);
            }
            /*
             * Les modificacions proposades el que fan es que en el cas de
             * delete en un dels strings, on no inserim el caracter, deixarem
             * que n sigui una unitat mes gran en l'altre string (al que li
             * representa un insert).
             *
             */
        }
    }

    /**
     * Genera les regles de mida maxima n a partir de la posicio i, j de la
     * matriu generada per l'algorisme de levenshtein M
     * 
     * @param M matriu generada per l'algorisme de levenshtein
     * @param s1 string *correcte* a partir del que es genera la part alpha de
     * les regles
     * @param s2 string *incorrecte* a partir del que es genera la part beta de
     * les regles
     * @param n mida maxima de les regles generades
     * @param i component i de la matriu a partir de la que generarem les regles
     * @param j component j de la matriu a partir de la que generarem les regles
     * @param rules conjunt de regles on afegirem les noves que es generin
     */
    private void levSubNAssociation(int [][] M,
            char [] s1, char [] s2, int n, int i, int j,
            ArrayList<ABPair> rules) {
        StringBuilder str1 = new StringBuilder();
        StringBuilder str2 = new StringBuilder();
        /*
         * ei i ej marquen el punt de la matriu en el que aconseguirem regles
         * de com a molt mida n
         */
        int ei = lowerLim(i-n);
        int ej = lowerLim(j-n);
        boolean [][] marks = new boolean[s2.length+1][s1.length+1];

        for (int k = 0; k < marks.length; ++k) {
            for (int l = 0; l < marks[0].length; ++l) {
                marks[k][l] = false;
            }
        }

        auxLevSubNAssociation(M, s1, s2, n, i, j, ei, ej, marks, rules,
                              str1, str2);
    }
    
    /**
     * Recorre tots els possibles camins minims del la matriu de levenshtein
     * donada i per cada posicio trovada es busquen les regles de mida maxima n
     * que es generen.
     *
     * @param s1 string *correcte* a partir del que es genera la part alpha de
     * les regles
     * @param s2 string *incorrecte* a partir del que es genera la part beta de
     * les regles
     * @param n mida maxima de les regles generades
     * @param i component i de la posicio que estem tractant
     * @param j component j de la posicio que estem tractant
     * @param rules conjunt de regles generades fins el moment
     * @param M matriu generada a partir de l'algorisme de levenshtein
     * @param marks matriu de marcatge per evitar solucions repetides.
     */
    private void auxLevNAssociation(String s1, String s2, int n, int i,
            int j, ArrayList<ABPair> rules, int [][] M, boolean [][] marks) {
        if (i > 0 && j > 0) {
            levSubNAssociation(M, s1.toCharArray(), s2.toCharArray(), n, i, j,
                               rules);
            marks[i][j] = true;
            int minPath = min3(M[i-1][j-1], M[i-1][j], M[i][j-1]);
            
            if (minPath == M[i-1][j-1] && !marks[i-1][j-1]) {
                    auxLevNAssociation(s1, s2, n, i-1, j-1, rules, M, marks);
            }
            if (minPath == M[i-1][j] && !marks[i-1][j]) {
                    auxLevNAssociation(s1, s2, n, i-1, j, rules, M, marks);
            }
            if (minPath == M[i][j-1] && !marks[i][j-1]) {
                    auxLevNAssociation(s1, s2, n, i, j-1, rules, M, marks);
            }
        }
    }

    /**
     * Genera totes les possibles regles de transformació de s1 a s2 de mida
     * maxima n. Les regles formades estan invertides.
     *
     * @param s1 representa una paraula *correcta*
     * @param s2 representa la paraula que el canal d'error generaria donat s1
     * @param n es la mida maxima que poden tenir els strings de les regles
     * @return un ArrayList de ABPair que conte totes les possibles regles
     * generades a partir de s1 i s2.
     */
    public ArrayList<ABPair> levNAssociation(String s1, String s2, int n) {
        int [][] M = levMatrix(s1.toCharArray(), s2.toCharArray());
        int j = s1.length();
        int i = s2.length();
        ArrayList<ABPair> rules = new ArrayList<ABPair>();
        boolean [][] marks = new boolean [M.length][M[0].length];
        
        for (int k = 0; k < marks.length; ++k) {
            for (int l = 0; l < marks[0].length; ++l) {
                marks[k][l] = false;
            }
        }
        
        auxLevNAssociation(s1, s2, n, i, j, rules, M, marks);

        return rules;
    }
}